package code1_100.code30_40;

import java.util.HashSet;
import java.util.Set;

/**
 * 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 *
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * 空白格用 '.' 表示。
 *
 * 输入：board =
 * [["5","3",".",".","7",".",".",".","."]
 * ,["6",".",".","1","9","5",".",".","."]
 * ,[".","9","8",".",".",".",".","6","."]
 * ,["8",".",".",".","6",".",".",".","3"]
 * ,["4",".",".","8",".","3",".",".","1"]
 * ,["7",".",".",".","2",".",".",".","6"]
 * ,[".","6",".",".",".",".","2","8","."]
 * ,[".",".",".","4","1","9",".",".","5"]
 * ,[".",".",".",".","8",".",".","7","9"]]
 * 输出：true
 *
 * 输入：board =
 * [["8","3",".",".","7",".",".",".","."]
 * ,["6",".",".","1","9","5",".",".","."]
 * ,[".","9","8",".",".",".",".","6","."]
 * ,["8",".",".",".","6",".",".",".","3"]
 * ,["4",".",".","8",".","3",".",".","1"]
 * ,["7",".",".",".","2",".",".",".","6"]
 * ,[".","6",".",".",".",".","2","8","."]
 * ,[".",".",".","4","1","9",".",".","5"]
 * ,[".",".",".",".","8",".",".","7","9"]]
 * 输出：false
 * 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
 *
 */
public class _36isValidSudoku {

    /**
     * 思考：只能遍历，难点在于九宫格的表示。技巧点在于1-9的次数的判断。本方法暴力遍历时间复杂度较高。
     * 方法二：题解只需要一次遍历，但空间复杂度较高，孰优孰劣暂不予置评
     *
     * 执行用时：     * 2 ms     * , 在所有 Java 提交中击败了     * 60.52%     * 的用户
     * 内存消耗：     * 38.4 MB     * , 在所有 Java 提交中击败了     * 81.99%     * 的用户
     * @param board
     * @return
     */
    public static boolean isValidSudoku(char[][] board) {
        Set<Character> set = new HashSet<>();
        char temp = ' ';
        // 判断行是否满足
        for (int i = 0; i < board.length; i++) {
            set.clear();
            for (int j = 0; j < board[0].length; j++) {
                temp = board[i][j];
                if(temp == '.')continue;
                if(!set.contains(temp)){
                    set.add(temp);
                }else {
                    return false;
                }
            }
            set.clear();
            for (int j = 0; j < board[0].length; j++) {
                temp = board[j][i];
                if(temp == '.')continue;
                if(!set.contains(temp)){
                    set.add(temp);
                }else {
                    return false;
                }
            }
        }
        // 判断矩形块是否满足
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                set.clear();
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        temp = board[i*3+k][j*3+l];
                        if(temp == '.')continue;
                        if(!set.contains(temp)){
                            set.add(temp);
                        }else {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    /**
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 37.8 MB     * , 在所有 Java 提交中击败了     * 98.91%     * 的用户
     *
     * 目前测试结果来看题解效率较高，是因为使用了数组而不是集合数据结构。
     * 题解使用int数组存储字符出现次数很好用，上述自己的题解可再优化
     * @param board
     * @return
     */
    public boolean isValidSudoku2(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
